\documentclass[a4paper,10pt, fleqn]{article}
\usepackage{graphicx} %Paquete para ingresar gráficos.
\usepackage{hyperref}
\usepackage{fancybox}
\usepackage[spanish]{babel} % Para división en sílabas español.
\usepackage[utf8]{inputenc} % Para poner acentos.
\usepackage{placeins} % Para poder usar \FloatBarrier para que las tablas e imagenes no se vayan de la seccion
\usepackage{float} % Para usar [H] en tablas e imagenes

% Título principal del documento.
\title{		\textbf{66:20 Organización de Computadoras\\Trabajo práctico 2: Profiling y optimización.}}

% Información sobre los autores.
\author{	ENRIQUEZ, Joaquín Javier, \textit{Padrón Nro. 87364}                     \\
            \texttt{ joaenriquez@gmail.com.ar }                                              \\
            ROMEO, Mauro Pedro, \textit{Padrón Nro. 89368}                    \\
            \texttt{ mauropromeo@hotmail.com }                                              \\
            \\
	    \normalsize{2do. Cuatrimestre de 2012}                       \\
            \normalsize{66.20 Organización de Computadoras}                             \\
            \normalsize{Facultad de Ingeniería, Universidad de Buenos Aires}            \\
       }
\date{6 de Diciembre del 2012}

\begin{document}

% Inserta el título.
\maketitle

% Resumen
\begin{abstract}
Familiarizarse con las técnicas y herramientas de profiling y optimización de software, evaluando y optimizando un programa determinado.

\end{abstract}
\newpage

\section{Enunciado}

\subsection{Objetivos}

Familiarizarse con las técnicas y herramientas de profiling y optimización de software, evaluando y optimizando un programa que implementa la simulación de un ecosistema de presas y depredadores [2].



\subsection{Alcance}

Este trabajo práctico es de elaboración grupal, evaluación individual, y de carácter obligatorio
para todos los alumnos del curso.

\subsection{Requisitos}
El trabajo deberá ser entregado personalmente, en la fecha estipulada, con una caratula que contenga los datos completos de todos los integrantes.
Ademas, es necesario que el trabajo práctico incluya (entre otras cosas, ver sección 1.8), la presentación de los resultados obtenidos, explicando, cuando corresponda, con fundamentos reales, las causas o razones de cada resultado obtenido.
El informe deberá respetar el modelo de referencia que se encuentra en el grupo, y se valoraran aquellos escritos usando la herramienta TEX / LATEX.

\subsection{Recursos}
Utilizaremos las herramienta gprof [3] y/o cachegrind [4] para evaluar la performance de las diversas áreas del programa y ver en cuáles se está empleando más tiempo.

\subsection{Introducción}
El planeta WA-TOR [1] está completamente cubierto de agua, y en él habitan principalmente plancton (que se supone infinito), peces (que viven del plancton), y tiburones (que comen peces). Este planeta es toroidal, de manera que su superficie se puede representar como una matriz rectangular, en la que al salir por un lado se vuelve a ingresar por el lado opuesto. Este planeta está modelado de la siguiente manera:
\begin{itemize}
\item \textbf{Cada celda puede contener o bien un pez, o un tiburón, o estar vacío.}
\item \textbf{En cada iteración del algoritmo, el habitante de cada celda puede intentar moverse:}
\begin{itemize}
\item \textbf{Si el habitante es un tiburón, y tiene algún pez en los casilleros adyacentes, se mueve a uno de estos casilleros elegido al azar, comiéndose al pez. De otra manera, si hay un casillero libre, se mueve a éste.}
\item \textbf{Si el habitante es un pez, y tiene algún casillero vacío adyacente, se mueve a alguno de estos al azar.}
\item \textbf{Al alcanzar una cierta edad, tanto los peces como los tiburones se reproducen, pero sólo si se pueden mover en ese turno. Al moverse, dejan detrás a otro habitante de su misma especie, y tienen que esperar una cantidad de turnos para volver a reproducirse.}
\item \textbf{Si un tiburón pasa cierta cantidad de turnos sin comer, muere y su casillero queda vacío.}
\end{itemize}
\end{itemize}
Los parámetros de esta simulación son entonces la edad a la que se reproducen los peces, la edad a la que se reproducen los tiburones, y la cantidad de tiempo que pueden pasar los tiburones sin comer. El objetivo del trabajo es evaluar el desempeño de un programa que simula la evolución de un grupo de peces y tiburones en el planeta WA-TOR, y de ser posible mejorarlo.

\subsection{Programa}
Se trata de una versión en lenguaje C de la simulación del planeta WA-TOR. El programa recibe un nombre de archivo en el que se van dejando las cantidades de peces y tiburones en cada turno, y simula 1000 turnos (o cronones) en un planeta de 32x32 celdas.


\subsection{Mediciones}
\subsubsection{Profiling}
Si bien la medida más simple y más definitiva de evaluar las mejoras en desempeño de un programa es el tiempo de ejecución, es difícil saber cómo optimizarlo si no tenemos claro cómo se distribuye el tiempo de ejecución entre las diferentes partes de éste. Una manera recomendada de proceder a la optimización de un programa consiste en ver en qué emplea más tiempo, y si esa sección de programa se puede hacer más eficiente. Por eso será necesario entonces detectar y documentar los principales cuellos de botella. Para esto, usaremos dos herramientas: cachegrind [4] y gprof [3].

\subsubsection{Caso de Prueba}
El caso que queremos analizar en cuanto a la performance del cache es el de una computadora con un cache L1D 2WSA de 256B, con 64 bytes por línea. Se simula en el cachegrind como
\begin{Verbatim}[fontsize=\tiny]
 valgrind --tool=cachegrind --D1=256,2,64 ./wator wator.txt
\end{Verbatim}
El miss rate del programa se puede ver con el cachegrind de la manera en que acabamos de ver. El gprof no permite la definición del cache donde corre el programa, pero permite ver cómo se reparte el tiempo de ejecución entre las distintas funciones y cuánto se llama a cada una. La función time de Linux también permite ver cuánto tiempo pasa el programa en modo usuario, cuánto en modo kernel, y cuánto dura la ejecución del programa. En clase veremos algunos ejemplos de utilización de estas herramientas.


\subsubsection{Documentación}
Es necesario que el informe incluya una descripción detallada de las técnicas y procesos de medición empleados, y de todos los pasos involucrados en el mismo, ya que forman parte de los objetivos principales del trabajo.

\subsection{Informe}
El informe deberá incluir:
\begin{itemize}
\item \textbf{Este enunciado.}
\item \textbf{Análisis de la performance del programa tal como está presentado, para el caso de prueba.}
\item \textbf{Optimizaciones planteadas y análisis de los cambios en performance.}
\item \textbf{El código fuente completo del programa modificado, en dos formatos: digital e impreso en papel.}
\end{itemize}

\subsection{Fecha de Entrega}
La ultima fecha de entrega y presentación es el jueves 13 de Diciembre de 2012.


 \begin{thebibliography}{99}

 
 \bibitem{WWW} ”Sharks and fish wage an ecological war on toroidal planet WA-TOR”, A.K.Dewdney, Scientific American,\url {http://home.cc.gatech.edu/biocs1/uploads/2/wator_dewdney.pdf.}
 \bibitem{WWW} WA-TOR, Wikipedia, \url{http://en.wikipedia.org/wiki/Wa-Tor.}
 \bibitem{WWW} GNU profiler, \url{http://sourceware.org/binutils/.}
 \bibitem{WWW} Cachegrind (parte del Valgrind), \url{http://valgrind.org/docs/.}
 
 \end{thebibliography}


\section{Desarrollo}
A continuación se muestra una breve explicación de las herramientas de profiling utilizadas, cómo compilar el programa, el código modificado y una explicacón de las partes de código que fueron modificadas y porque fueron modificadas. También se analiza la repersución que tuvieron los cambios en los tiempos de ejecución y en los accesos a memoria y misses.

\subsection{Herramientas de Profiling}
\subsubsection{gprof}
El gprof es una herramienta de análisis de rendimiento de Unix. Es una extensión de la vieja herramienta de Unix "prof". A diferencia de prof, gprof es capaz de hacer análisis de gráficos de llamadas.
Se debe compilar el código con la opción -pg. Esto sirve para recolectar información del caller. También se insertan llamadas a la función especial de monitoreo 'mcount' antes de cada llamada a función. Luego se corre el programa de la siguiente forma:\\
gprof wator >wator.stats\\
Luego en wator.stats se pueden ver los tiempos de ejecución de cada función y que porcentage ocupan en el tiempo de ejecución total. Aquí podremos ver cual es la función que más tiempo se ejecuta durante el programa para luego poder intentar optimizarla. 

\subsubsection{cachegrind}
Cachegrind es una herramienta de valgrind que simula como trabaja un cache con un determinado programa. Simula una con un L1 split (I1 y D1) y un L2 unificado. Esta herramienta nos permite ver la cantidad de referencias que hace el programa a memoria junto con los misses en los distintos niveles de la cache. También nos muestra los miss rate los cuales van a ser utilizados para intenter optimizar el programa.\\
El caso que queremos analizar en cuanto a la performance del cache es el de una computadora con un cache L1D 2WSA de 256B, con 64 bytes por línea. Se simula de la siguiente forma:\\
valgrind --tool=cachegrind --D1=256,2,64 ./wator wator.txt

\subsubsection{time}
Esta herramienta nos sirve para saber cuanto tiempo tarda en ejecutarse el programa. Nos dice cuanto tiempo tarda en modo usuario y cuanto en modo kernel.\\
Se utiliza de la siguien forma:\\
time ./wator

\subsection{Compilado y Modo de Uso}
Para compilar el programa ejecutamos:\\
gcc -O0 wator.c -o wator\\
Y para correr el programa:
./wator wator.txt\\
En wator.txt se escribiran las cantidades peces y tiburones de cada turno.

\subsection{Análisis sin profiling y mejoras}
Primero se realizó un análisis del código para ver que partes se podían optimizar a simple vista.
En el struct animal se cambiaron los atributos kind que era un int por un char, age que era un int a short int, y hunger que era un int a short int. Como los turnos son 1000, no era necesario tener int en hunger y edad, y como solo tenemos dos tipos de animales con un char basta para representar los distintos tipos.
También se sacaron todos los assert del código ya que se supone que el programa nunca va a tomar valores no permitidos.
Algo que se notó en muchas funciones es que cada vez que se necesita acceder a una posición de la matriz se llama a \&wator[x][y] y luego cuando se quiere usar la misma posición, se vuelve a llamar a lo mismo. Lo que se hizo fue guardar \&wator[x][y] en un puntero a una struct animal y de esta forma se va a resolver la variable una sola vez. Esta es una optimización importante ya que se repite a lo largo de todo el código, para cada iteración.
En la funcion show\_wator se llamaba a un printf por cada casillero, lo que genera segun lo aprendido durante el cusro, una llamada costasa al sistema. Para mejorar esto, se concateno cada casillero en una sola cadena por cada iteracion, logrando reducir de 32*32 llamadas a printf a solo 1 por iteracion de simulacion.
Por ultimo en moveall también se realizó una mejora sacando un for que era innecesario, dado que la condicion de su if interno, inderectamente, era la misma que la del for que estaba a continuacion

\subsection{Análisis con profiling y mejoras}
Luego se procedió a correr el programa con los programas de profiling.
La salida del gprof es la siguiente:\\

Flat profile:

Each sample counts as 0.01 seconds.
\begin{verbatim} 
 
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 23.12      0.06     0.06  2477076     0.02     0.02  ni
 19.27      0.11     0.05  2477076     0.02     0.02  nj
 19.27      0.16     0.05   468812     0.11     0.30  choose_empty
 15.41      0.20     0.04     1000    40.08   260.47  moveall
 11.56      0.23     0.03   468812     0.06     0.38  move_to_empty
  3.85      0.24     0.01   537037     0.02     0.41  move
  3.85      0.25     0.01   255380     0.04     0.04  myrand
  3.85      0.26     0.01    86868     0.12     0.34  move_to_fish
  0.00      0.26     0.00    86868     0.00     0.20  choose_fish
  0.00      0.26     0.00    68637     0.00     0.00  new_animal
  0.00      0.26     0.00     1001     0.00     0.00  show_wator
  0.00      0.26     0.00        1     0.00    40.18  init_wator
\end{verbatim} 
Las columnas mas significativas de esta salida son la de \% time que nos dice el porcentaje que ocupa la función en el tiempo total de ejecución y la columna self seconds que nos dice la cantidad total de segundos que tarda el programa en en ejecutar esta función.\\
Se puede observar que la funciones que consumen mas tiempo son ni, nj y choose\_empty.\\
Primero se analizó choose\_empty y vimos que se podia mejorar mucho. Esta función llama constantemente a la función ni y nj para obtener las coordenas de los casilleros que rodean al actual. Nos dimos cuenta que se podia reducir la llamadas a ni, ya que el valor seria el mismo para toda una fila y lo guardamos en variables globales llamadas ninorth y nisouth. También se hizo lo mismo para el cálculo de npi. Estos cambios se hicieron tanto en choose\_empty como en choose\_fish y moveall ya que tienen lógicas parecidas.
El ni y el nj no se pudieron optimizar directamente pero, por lo dicho antes, se redujo significativamente las llamadas a ni reduciendo el tiempo final de ejecución.\\

Este es el resultado de la corrida del programa con cachegrind:\\
\\
\begin{verbatim}
==4753== 
==4753== I   refs:      421,649,062
==4753== I1  misses:          9,937
==4753== LLi misses:            919
==4753== I1  miss rate:        0.00%
==4753== LLi miss rate:        0.00%
==4753== 
==4753== D   refs:      186,602,500  (131,024,416 rd   + 55,578,084 wr)
==4753== D1  misses:     33,075,569  ( 27,119,081 rd   +  5,956,488 wr)
==4753== LLd misses:          1,847  (      1,121 rd   +        726 wr)
==4753== D1  miss rate:        17.7% (       20.6%     +       10.7%  )
==4753== LLd miss rate:         0.0% (        0.0%     +        0.0%  )
==4753== 
==4753== LL refs:        33,085,506  ( 27,129,018 rd   +  5,956,488 wr)
==4753== LL misses:           2,766  (      2,040 rd   +        726 wr)
==4753== LL miss rate:          0.0% (        0.0%     +        0.0%  )
\end{verbatim}
Y este es el tiempo de ejecución del programa original corrido en MIPS:\\
real    0m33.184s\\
user    0m24.875s\\
sys     0m8.320s\\

\subsection{Código Mejorado}
\begin{verbatim}[fontsize=\tiny]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define EMPTY 0
#define SHARK 1
#define FISH  2

struct animal {
	unsigned char kind;     /* SHARK o FISH */ //mejora, cambio de int por unsigner char
	short int age;      /* Edad del animal. */ //mejora, cambio de int por short int
	short int hunger;   /* Turnos que lleva sin comer un tiburón */ // mejora, cambio de int por short int
    // mejora, se saco propiedad "todo", no se usaba
}animal;

#define MAXI 32
#define MAXJ 32
int HBRUT, FBRUT, FASTEN;

struct animal wator[MAXI][MAXJ] ;

#define REST -1
#define NORTH 0
#define SOUTH 1
#define EAST 2
#define WEST 3

int ninorth = 0;
int nisouth = 0;

int ni (int i, int dir)
{
	switch (dir) {
	case NORTH:
		return (i+MAXI-1) % MAXI;
	case SOUTH:
		return (i+1) % MAXI;
    case EAST:
    case WEST:
        return i;
//	default:
//		assert (0);
	}
	return -1;
}

int nj (int j, int dir)
{
	switch (dir) {
	case EAST:
		return (j+MAXJ-1) % MAXJ;
	case WEST:
		return (j+1) % MAXJ;
    case NORTH:
    case SOUTH:
        return j;
//	default:
//		assert (0);
	}
	return -1;
}

int newcount = 0;

void new_animal (int i, int j, char kind)
{
	struct animal *t = & wator[i][j] ;
	t->kind = kind;
	t->age = 0;
	t->hunger = 0;
	newcount++;
}

int myrand (int max)
{
	return rand () % max;
}

int choose_fish (int i, int j)
{
	int k = 0;
	int dir = 2;
	int dirs[4];
    struct animal * t;
    
    //mejora: nisouth y ninorth precalculado para toda la fila i
    t = &wator[ninorth][j];
	if (t->kind == FISH) {
		dirs[k] = NORTH;
		k++;
	}
    
    t = &wator[nisouth][j];
	if (t->kind == FISH) {
		dirs[k] = SOUTH;
		k++;
	}

	for (dir=2; dir < 4; dir++) { 
        //mejora, no llamar a npi ya que da i
    	int npx;
    	npx = nj (j, dir);
	    t = &wator[i][npx];
		if (t->kind == FISH) {
			dirs[k] = dir;
			k++;
		}
	}
	if (k == 0)
		return REST;
	return dirs[myrand (k)];
}

int choose_empty (int i, int j)
{
	int k = 0;
	int dir = 2;
	int dirs[4];
    struct animal * t;
    
    //mejora: nisouth y ninorth precalculado para toda la fila i
    t = &wator[ninorth][j];
	if (t->kind == EMPTY) {
		dirs[k] = NORTH;
		k++;
	}
    
    t = &wator[nisouth][j];
	if (t->kind == EMPTY) {
		dirs[k] = SOUTH;
		k++;
	}

	for (dir=2; dir < 4; dir++) { 
        //mejora, no llamar a npi ya que da i
    	int npx;
    	npx = nj (j, dir);
	    t = &wator[i][npx];
		if (t->kind == EMPTY) {
			dirs[k] = dir;
			k++;
		}
	}
	if (k == 0)
		return REST;
	return dirs[myrand (k)];
}

int freecount = 0;

int move_to_fish (int i, int j)
{
	int npi, npj;
	int dir;
	struct animal * t;
	struct animal * n;

	t = &wator[i][j];

	dir = choose_fish (i, j);
	if (dir == REST)
		return 0;
	npi = ni (i, dir);
	npj = nj (j, dir);

    n = &wator[npi][npj];

	freecount++;
	memcpy  (n, t,sizeof(animal));
	t->kind = EMPTY;
	n->hunger = 0;
	if (wator[npi][npj].age >= HBRUT) {
		t->age = 0;
		new_animal (i, j, SHARK);
	}
	return 1;
}

int move_to_empty (int i, int j)
{
	int npi, npj;
	int dir;
	struct animal * t;
    struct animal * n;

	t = &wator[i][j];

	dir = choose_empty (i, j);
	if (dir == REST)
		return 0;
	npi = ni (i, dir);
	npj = nj (j, dir);
    n = &wator[npi][npj];
	memcpy(n, t, sizeof(animal));//copia el animal a la nueva posicion
	t->kind = EMPTY;//"nullea" la vieja
	if ((n->kind == FISH) && (n->age >= FBRUT)) { //reproduccion del fish
		n->age = 0;
		new_animal (i, j, FISH);
	}
	if ((n->kind == SHARK) && (n->age >= HBRUT)) {//reproduccion del shark
		n->age = 0;
		new_animal (i, j, SHARK);
	}
	return 1;
}

void move (int i, int j)
{
	struct animal * t;
	t = &wator[i][j];
	t->age++;
	if (t->kind == SHARK) {
		t->hunger++;
		if (t->hunger >= FASTEN) {//si el tiburon tiene mas hambre que lo permitido, muere
			wator[i][j].kind = EMPTY;
			freecount++;
			return;
		}

		if (move_to_fish (i, j)) //si tiene un pez adyacente se lo morfa
			return;
	}
	move_to_empty (i, j); //busca un lugar vacio adonde moverse
}

int fd = -1;

void show_wator ()
{
	int i, j;
	short int shark = 0, fish = 0;
	char aux[MAXI*(MAXJ+1)+1];
	for (i=0; i<MAXI; ++i) {
		for (j=0; j<MAXJ; ++j) {
			if (wator[i][j].kind != EMPTY) {
				if (wator[i][j].kind == SHARK) {
					aux[i*(MAXJ+1)+j] = 'X';
					shark++;
				} else {
					aux[i*(MAXJ+1)+j] = '*';
					fish++;
				}
			} else {
				aux[i*(MAXJ+1)+j] = '.';
			}
		}
		aux[i*(MAXJ+1)+j] = '\n';
		
	}
	aux[MAXI*(MAXJ+1)]='\0';

	printf ("%s SHARKS: %d, FISH: %d NEW: %d, FREE: %d\n\n", aux, shark, fish, newcount, freecount);
// cambio 32x32 printf por uno solo

	if (fd >= 0) {
		char buf[20];//mejora: se achico el buffer de 100 a 20
		int ret;
		static int tick = 0;
		sprintf (buf, "%d %d %d\n", tick, shark, fish);
		tick++;
		ret = write (fd, buf, strlen (buf));
		if (ret != strlen (buf)) {
			fprintf (stderr, "Write to output file failed\n");
			exit (2);
		}
	}
	newcount = freecount = 0;
}

void init_wator (int maxi, int maxj, int hbrut, int fbrut, int fasten)
{
	int i, j;
	HBRUT = hbrut;
	FBRUT = fbrut;
	FASTEN = fasten;
	//assert (hbrut > FASTEN);
	for (i=0; i<MAXI; ++i) {
		for (j=0; j<MAXJ; ++j) {
			int res = myrand (30);
			wator[i][j].kind = EMPTY;
			switch (res) {
			case 0:
				new_animal (i, j, SHARK);
				break;
			case 1 ... 11:
				new_animal (i, j, FISH);
				break;
			}
		}
	}
}
//saco un for entero q es innecesario y saco la variable "todo"
void moveall ()
{
	int i, j;
	for (i=0; i<MAXI; ++i) {
        ninorth = ni (i,NORTH);//mismo para toda la fila
        nisouth = ni (i,SOUTH);//mismo para toda la fila
		for (j=0; j<MAXJ; ++j) {
			if (wator[i][j].kind !=EMPTY) {
				move (i, j);
			}
		}
	}
}

int main (int argc, char * argv[])
{

	int i;
	srand (time (NULL));
	fd = -1;
	if (argc > 2) {
		fprintf (stderr, "usage: wator [ file ]\n");
		exit (1);
	}
	if (argc == 2) {
		fd = open (argv[1], O_WRONLY|O_TRUNC|O_CREAT, 0600);
		if (fd < 0) {
			perror ("open");
			exit (1);
		}
	}

	
	init_wator (MAXI, MAXJ, 10, 3, 3);
	show_wator ();
	for (i=0;i<1000;i++) {
		moveall ();
		show_wator ();
	}
	return 0;
}

\end{verbatim}

\subsection{Corridas con mejoras}
Esta es la salida del gprof del programa mejorado:\\
\\
Each sample counts as 0.01 seconds.
\begin{verbatim}
 %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 13.36      0.02     0.02  1500096     0.01     0.01  ni
 13.36      0.04     0.02   510195     0.04     0.11  choose_empty
 13.36      0.06     0.02   510195     0.04     0.16  move_to_empty
 13.36      0.08     0.02   416730     0.05     0.05  myrand
 13.36      0.10     0.02   141166     0.14     0.18  choose_fish
 13.36      0.12     0.02     1000    20.04   140.24  moveall
  6.68      0.13     0.01  1718428     0.01     0.01  nj
  6.68      0.14     0.01   618943     0.02     0.19  move
  6.68      0.15     0.01     1001    10.01    10.01  show_wator
  0.00      0.15     0.00   141166     0.00     0.19  move_to_fish
  0.00      0.15     0.00   109201     0.00     0.00  new_animal
  0.00      0.15     0.00        1     0.00    49.25  init_wator
\end{verbatim}

Se puede observar que la columna self seconds bajo para casi todas las funciones, en especial para ni, nj y choose\_empty. Para ni bajo de 0.06 a 0.02, para nj bajo de 0.05 a 0.01 y para choose\_empty bajo de 0.05 a 0.02. También se puede apreciar que la suma de todos los tiempos de las funciones que es el cumulative seconds del final bajo de 0.26 a 0.15.\\

Esta es la salida del cachegrind del programa mejorado:\\
\begin{verbatim}
==4793== 
==4793== I   refs:      294,447,397
==4793== I1  misses:          6,946
==4793== LLi misses:            925
==4793== I1  miss rate:        0.00%
==4793== LLi miss rate:        0.00%
==4793== 
==4793== D   refs:      113,645,669  (77,528,046 rd   + 36,117,623 wr)
==4793== D1  misses:     14,436,300  (10,829,438 rd   +  3,606,862 wr)
==4793== LLd misses:          1,711  (     1,120 rd   +        591 wr)
==4793== D1  miss rate:        12.7% (      13.9%     +        9.9%  )
==4793== LLd miss rate:         0.0% (       0.0%     +        0.0%  )
==4793== 
==4793== LL refs:        14,443,246  (10,836,384 rd   +  3,606,862 wr)
==4793== LL misses:           2,636  (     2,045 rd   +        591 wr)
==4793== LL miss rate:          0.0% (       0.0%     +        0.0%  )

\end{verbatim}
Aquí se puede apreciar que las referencias a memoria bajaron considerablemente en el cache de instrucciones de nivel uno, de un total de 400 millones aproximadamente bajaron a 290 millones. También bajaron los misses de 9,937 a 6,946. El miss rate no es significativo comparado con la cantidad de referencias a memoria.\\
En el cache de datos de nivel 1 las referencias a memoria bajaron de 186 millones a 113 y los misses de 33 millones a 14 millones que se reparten entre lecturas y escrituras. El miss rate bajo de 17.7\% a 12.7\%.\\
En el cache de nivel 2 que es unificado las referencia a memoria bajaron de 33 millones a 14 millones y los misses y el miss rate se mantuvieron aproximadamente iguales. El miss rate no es significativo comparado con la cantidad de referencias a memoria.\\
\\
Y este es el tiempo de ejecución del programa mejorado corrido en MIPS:\\
real    0m19.203s\\
user    0m8.340s\\
sys     0m10.844s\\
\\
Aquí se muestra que el tiempo de ejecución total del programa bajo de 0m33.184s a 0m19.203s lo que muestra que el programa efectivamente fue optimizado.

\subsection{Conclusiones}

Mediante este trabajo práctico se pudo aplicar los conocimientos de arquitectura aprendidos durante la materia. Se analizó código fuente de un programa para luego optimizarlo significativamente en función de la disposicion de cache elegida y el conocimiento de Assembly, ya que nos permitio saber que resolver posiciones de memoria de un vector tiene un costo, asi como una llamada al sistema o que modificar como se recorren vectores puede mejorar significativamente el rendimiento.\\
Por otro lado, para realizar lo antes mencionado, tuvimos una introduccion a herramientas de profiling y pudimos conocer lo importante y utiles que pueden ser para el desarrollo de cualquier sistema, para asegurar su buen rendimiento.\\

\begin{thebibliography}{99}

 \bibitem{WWW} ”Sharks and fish wage an ecological war on toroidal planet WA-TOR”, A.K.Dewdney, Scientific American,\url {http://home.cc.gatech.edu/biocs1/uploads/2/wator_dewdney.pdf.}
 \bibitem{WWW} WA-TOR, Wikipedia, \url{http://en.wikipedia.org/wiki/Wa-Tor.}
 \bibitem{WWW} GNU profiler, \url{http://sourceware.org/binutils/.}
 \bibitem{WWW} Cachegrind (parte del Valgrind), \url{http://valgrind.org/docs/.}
 
 \end{thebibliography}



\end{document}
